package lib

import (
	"sort"
)


func init() {
	Probs = append(Probs, Problem{
		Num:         16,
		Discription: "最接近的三数之和",
		Level:       2,
		Labels: map[string]int{
			"双指针滑动": 1,
			"排序":    1,
			"去重":    1,
		},
	})
}

func ThreeSumClosest(nums []int, target int) int {
	nearstSum := nums[0] + nums[1] + nums[2]
	sort.Ints(nums)
	n := len(nums)
	for i := 0; i <= n-3; i++ {
		for i > 0 && i <= n-3 && nums[i] == nums[i-1] {
			i++
		}

		left := i + 1
		right := n - 1
		for left < right {
            //找到本体直接退
			sum := nums[i] + nums[left] + nums[right]
            if sum==target{
                return target
            }

			if abs(sum-target) < abs(nearstSum-target) {
                nearstSum=sum
			}

            //无论有无更新最接近的值，都需要更新双指针，且只需更新一边
            if sum<target{
                left++
                for left<right&&nums[left]==nums[left-1]{
                    left++
                }
            }else{
                right--
                for left<right&&nums[right]==nums[right+1]{
                    right--
                }
            }
		}
	}

    return nearstSum
}

func abs(a int)int{
    if a>=0{
        return a 
    }

    return -a
}
